1. МЕТОДИ РОЗВ’ЯЗУВАННЯ СИСТЕМ
ЛІНІЙНИХ АЛГЕБРИЧНИХ РІВНЯНЬ
Розглянемо чисельні методи розв’язування систем лінійних алгебричних рівнянь
EMBED Equation.3 , (1)
де A - матриця m*m, EMBED Equation.3 - шуканий вектор, EMBED Equation.3 - заданий вектор.
Припускаємо, що EMBED Equation.2 та визначник матриці А відмінний від нуля, так що існує єдиний розв’язок Х. З курсу алгебри відомо, що систему (1) можна розв’язати за формулами Крамера1. Для великих m цей спосіб практично нереалізований тому, що потребує порядку m! aрифметичних дій. Тому широко використовуються інші методи розв’язування, наприклад, метод Гауса2, який потребує EMBED Equation.2 дій.
Методи чисельного розв’язування системи (1) поділяються на дві групи:
- прямі методи;
- ітераційні методи.
У прямих (або точних) методах розв’язок Х системи (1) відшукується за скінченну кількість арифметичних дій. Внаслідок похибок заокруглення прямі методи насправді не приводять до точного розв’язку системи (1) і назвати їх точними можливо лише залишаючи осторонь похибки заокруглення.
Ітераційні методи (їх також називають методами послідовних наближень) полягають у тому, що розв’язок x системи (1) відшукується як границя при EMBED Equation.3 послідовних наближень EMBED Equation.3 де n- номер ітерації. Як правило, за скінченну кількість ітерацій ця границя не досягається.
1.1. МЕТОД ГАУСА
Запишемо систему (1) у розгорнутому вигляді:
EMBED Equation.3 (2)
Метод Гаусса розв’язання системи (2) полягає у послідовному вилученні невідомих EMBED Equation.3 з цієї системи.
Припустимо, що EMBED Equation.3 . Поділивши перше рівняння на EMBED Equation.3 , отримаємо
EMBED Equation.3 , (3)
де EMBED Equation.3
Розглянемо тепер рівняння системи (2), що залишилися
EMBED Equation.3 . (4)
Помножимо (3) на EMBED Equation.3 та віднімемо одержане рівняння з і-го рівняння системи (4), EMBED Equation.3 .
У результаті отримаємо наступну систему рівнянь
EMBED Equation.3 (5)
Tут позначено:
EMBED Equation.3 . (6)
Матриця системи (5) має вигляд:
EMBED Equation.3 .
Матриці такої структури заведено позначати так:
EMBED Equation.3 ,
де хрестиками позначені ненульові елементи.
У системі (5) невідоме х міститься тільки в першому рівнянні, тому у подальшому достатньо мати справу із скороченою системою рівнянь:
EMBED Equation.3 (7)
Тим самим ми здійснили перший крок методу Гаусса. Коли EMBED Equation.2 , то з системи (7) зовсім аналогічно можна вилучити невідоме x2 і прийти до системи, еквівалентній (2),що має матрицю такої структури:
EMBED Equation.3 . (8)
При цьому перше рівняння системи (5) залишається без зміни.
Вилучаючи таким же чином невідомі EMBED Equation.3 , приходимо остаточно до системи рівнянь виду
EMBED Equation.3 (9)
що еквівалентна початковій системі (2).
Матриця цієї системи
EMBED Equation.3 (10)
містить нулі усюди нижче головної діагоналі. Матриці такого виду називаються верхніми трикутними матрицями. Нижньою трикутною матрицею називається така матриця, у якої дорівнюють нулю усі елементи, що містяться вище головної діагоналі.
Побудова системи (9) складає прямий хід методу Гаусса. Зворотний хід полягає у відшуканні невідомих EMBED Equation.3 з системи (9). Тому що матриця системи має трикутний вигляд, можна послідовно, починаючи з EMBED Equation.3 , відшукати всі невідомі. Дійсно,
EMBED Equation.3 , ...
Загальні форми зворотного ходу мають вигляд
EMBED Equation.3 (11)
...
